96

8

Sets and Combinatorics

StartBinomialOrMatrix n Choose r EndBinomialOrMatrix equals StartBinomialOrMatrix n Choose n minus r EndBinomialOrMatrix for r equals 0 comma 1 comma period period period comma n semicolon

(n

r

)

=

(

n

n −r

)

for r = 0, 1, ..., n ;

(8.9)

in words, for example, selecting five objects out of nine is the same as selecting four

to be omitted.

It is implied that the selections are independent. In practical problems, this may

be far from reality. For example, a manufacturer assembling engines from 500 parts

may have to choose from a total of 9000. The number of combinations is at first

sight a huge number, 9000 factorial slash left parenthesis 500 factorial 8500 factorial right parenthesis tilde 10 Superscript 8409000!/(500! 8500!) ∼10⁸⁴⁰ by Stirling’s approximation, pos-

ing a horrendous logistics problem. Yet many of the choices will fix others; strong

constraints drastically reduce the freedom of choice of the components.

Partitioning

The number of ways in whichnn elements can be partitioned intokk subpopulations, the

first containingr 1r1 elements, the secondr 2r2, and so on, wherer 1 plus r 2 plus midline horizontal ellipsis plus r Subscript k Baseline equals nr1 + r2 + · · · + rk = n, is

given by multinomial coefficientsn factorial slash left parenthesis r 1 factorial r 2 factorial midline horizontal ellipsis r Subscript k Baseline factorial right parenthesisn!/(r1!r2! · · ·rk!), obtained by repeated application

of Eq. (8.8). If rr balls are placed in nn cells with occupancy numbers r 1 comma r 2 comma ellipsis comma r Subscript n Baseliner1,r2, . . . ,rn,

with all n Superscript rn^r possible placements equally possible, then the probability to obtain a set

of given occupancy numbers equals n Superscript negative r Baseline n factorial slash left parenthesis r 1 factorial r 2 factorial ellipsis r Subscript k Baseline factorial right parenthesisn^−rn!/(r1!r2! . . .rk!) (the Maxwell–Boltzmann

distribution). This multinomial coefficient will be denoted using square brackets:

StartBinomialOrMatrix r Choose r Subscript i Baseline EndBinomialOrMatrix equals StartFraction n factorial Over r 1 factorial r 2 factorial midline horizontal ellipsis r Subscript k Baseline factorial EndFraction comma with sigma summation Underscript i Overscript i equals k Endscripts r Subscript i Baseline equals n period

[ r

ri

]

=

n!

r1!r2! · · ·rk! ^,

with

i=k

∑

i

ri = n .

(8.10)

Fermi–Dirac Statistics

Fermi–Dirac statistics are based on the following hypotheses: (i) No more than one

element can be in any given cell (hence r less than or equals nr ≤n) and (ii) all distinguishable arrange-

ments satisfying (i) have equal probabilities.

By virtue of (i), an arrangement is completely specified by stating which of thenn

cells contain an element; since there arerr elements, the filled cells can be chosen in

StartBinomialOrMatrix n Choose r EndBinomialOrMatrix

(n

r

)

ways, each with probability StartBinomialOrMatrix n Choose r EndBinomialOrMatrix Superscript negative 1

(n

r

)−1.

Bose–Einstein Statistics

Let the occupancy numbers of the cells be given by

r 1 plus r 2 plus midline horizontal ellipsis plus r Subscript n Baseline equals r periodr1 + r2 + · · · + rn = r .

(8.11)

The number of distinguishable distributions (if the elements are indistinguishable,

distributions are distinguishable only if the corresponding nn-tuples left parenthesis r 1 comma ellipsis comma r Subscript n Baseline right parenthesis(r1, . . . ,rn) are

not identical) is the number of different solutions of Eq. (8.11). We call this upper A Subscript r comma nAr,n

(given by Eq. 8.13) and each solution has the probability upper A Subscript r comma n Superscript negative 1A⁻¹

r,n ^{of occurring.}

Problem. Consider a sequence of two kinds of elements:aa alphas, numbered 1 toaa,

andbb betas numbereda plus 1a + 1 toa plus ba + b. Show that the alphas and betas can be arranged

in exactly